Problema do empacotamento

No problema de bin packing (ou problema do empacotamento), objetos de diferentes volumes devem ser embalados em um número finito de bandejas ou recipientes de volume V de uma forma que minimize o número de recipientes utilizados. Na teoria da complexidade computacional, este é um problema de combinatória NP-difícil.^[1] O problema de decisão (decidir se um determinado número de pacotes é o ideal) é NP-completo.^[2]

Existem muitas variações deste problema, tais como empacotamento 2D (2D packing), empacotamento linear (linear packing), empacotamento por peso (packing by weight), empacotamento por custo (packing by cost), e assim por diante. Eles tem muitas aplicações, tais como o enchimento de recipientes, carregamento de caminhões com peso com capacidade restrita, criação de arquivo de backup (cópias de segurança) em mídia.

O problema do empacotamento também pode ser visto como um caso especial do problema de corte de estoque (cutting stock problem). Quando o número de pacotes é restrito a 1 e cada item é caracterizado por um volume e um valor, o problema de maximização do valor dos itens que podem caber na lixeira é conhecida como a problema da mochila.

Apesar do fato de que o problema do empacotamento tem uma complexidade computacional uma NP-difícil, as melhores soluções para grandes instâncias do problema pode ser produzido com algoritmos sofisticados. Além disso, muitas heurísticas foram desenvolvidas: por exemplo, o algoritmo de first fit fornece uma solução rápida, mas muitas vezes não ideal, envolvendo colocar-se cada item para a primeira posição que couber. Ele requer custo de tempo Θ(n log n), onde n é o número de elementos a ser empacotados. O algoritmo pode ser tornado mais eficaz se primeiramente ordenar a lista de elementos em ordem decrescente (às vezes conhecida como o algoritmo first-fit decrescente), embora isso ainda não garante uma solução ótima, e para longas listas pode aumentar o tempo de execução do algoritmo. Sabe-se, contudo, que existe sempre pelo menos um ordenamento de itens que o first-fit produzir uma solução ótima.^[3]

Um variante do bin packing que ocorre na prática é quando os itens podem compartilhar o espaço quando empacotados em uma caixa. Especificamente, um conjunto de itens pode ocupar menos espaço quando embaladas em conjunto do que a soma de seus tamanhos individuais. Esta variante é conhecida como VM packing^[4] desde quando máquinas virtuais (VMs) são embaladas em um servidor, o total de sua memória gerenciada pode diminuir devido às páginas compartilhadas pelas VMs as quais precisam ser armazenados apenas uma vez. Se os itens podem dividir o espaço de maneiras arbitrárias, o problema do empacotamento é difícil, mesmo de forma aproximada. No entanto, se o compartilhamento de espaço se encaixa em uma hierarquia, como é o caso de compartilhamento de memória em máquinas virtuais, o problema do empacotamento pode ser eficientemente aproximado.

↑ Korte, Bernhard; Vygen, Jens (2006). «Bin-Packing». Combinatorial Optimization: Theory and Algorithms. Col: Algorithms and Combinatorics 21. [S.l.]: Springer. pp. 426–441. ISBN 978-3-540-25684-7. doi:10.1007/3-540-29297-7_18
↑ Barrington, David Mix (2006). «Bin Packing»
↑ Lewis 2009
↑ Sindelar, Sitaraman & Shenoy 2011, pp. 367–378

[1] Korte, Bernhard; Vygen, Jens (2006). «Bin-Packing». Combinatorial Optimization: Theory and Algorithms. Col: Algorithms and Combinatorics 21. [S.l.]: Springer. pp. 426–441. ISBN 978-3-540-25684-7. doi:10.1007/3-540-29297-7_18

[2] Barrington, David Mix (2006). «Bin Packing»

[3] Lewis 2009

[4] Sindelar, Sitaraman & Shenoy 2011, pp. 367–378

[1]

[2]

[3]

[4]